package dataStructure.LinkList;

/*单链表*/
public interface LinkList {
    // 返回头节点
    Node  getHead();
    // 头插法  逆序添加
    void addFirst(int data);

    // 尾插法 顺序添加
    void addLast(int data);

    // 任意位置插入，第一数据节点为0号下标
    boolean addIndex(int index, int data);

    // 查找是否包含关键字 key 在单链表中
    boolean contains(int data);
    // 按值查询
    Node searchNodeByData(int data);

    // 删除第一次出现的关键字为 key 的节点
    boolean remove(int data);

    // 删除所有值为 key 的节点
    void removeAllKey(int data);

    boolean updateNodeByIndex(int index,int data);

    // 得到单链表的长度
    int size();

    // 打印单链表
    void display();

    // 清空单链表以防内存泄漏
    void clear();

    Node acquireLastNode();

    // 找最小值节点
    Node searchMinNode ();

    // 找最小值的前驱节点
    Node getMinNodePre();
    // 根据索引找节点
    Node searchNodeByIndex(int index);
}

class SLinkList implements LinkList{

    //private Node head = null; // 默认头节点   不带头节点的
    private Node head = new Node(-1); // 默认头节点  带头节点的

    //返回头节点
    @Override
    public Node getHead() {
        return head;
    }

    @Override
    public void addFirst(int data) {
        Node temp = this.head;
        Node node = new Node(data);
        if(this.head==null) {
            this.head=node;
            return;
        }
        node.next = temp.next;//注意两者不能颠倒顺序（自己可以尝试一下如果颠倒链表将接不上），节点都是先连接才能保证链表的连接
        temp.next= node;
    }

    @Override
    public void addLast(int data) {
        Node node=new Node(data);
        if(this.head==null) {  //如果链表为空，直接插入
            this.head=node;
            return;
        }
        Node temp = this.head;   //创建cur用来表示目前节点
        while(temp.next != null){//设置循环让cur往后走，当cur到最后一个节点时停止循环
            temp = temp.next;     //cur后移
        }
        temp.next = node;  //最后一个节点接上尾巴
    }

    // 先封装一个方法用来找指定位置 的节点
    @Override
    public Node searchNodeByIndex(int index) {  // 头结点索引是0 第一个元素索引是1
        if(index<0||index>this.size()){  //判断位置合法性
            throw new RuntimeException("index位置不合法");
        }
        if (index==0){
            return this.head; // 头结点就是第一个节点
        }
        Node temp = this.head;
        int count = 0;
        while (count != index) {//找到指定位置的节点
            count++;
            temp=temp.next;
        }
        return temp;
    }

    /*在指定索引处添加节点*/
    @Override
    public boolean addIndex(int index, int data) {
        // 空链表直接头插
        if(size()==0) {
            this.addFirst(data);
            return true;
        }

        if (size() == index){
            Node node = new Node(data);
            Node lastNode = acquireLastNode();
            lastNode.next = node;
            node.next = null;
            return true;
        }
        Node node = new Node(data);
        Node temp = searchNodeByIndex(index);

        if(temp !=null){
            node.next = temp.next;
            temp.next = node;
            return true ;
        }
        return false;
    }

    /*获取最后一个节点*/
    @Override
    public Node acquireLastNode(){
        if (size()==0){
            throw new RuntimeException("当前没有节点 获取最后一个节点失败");
        }
        Node temp = this.head;
        while (temp.next!=null){
            temp = temp.next;
        }
        return temp;
    }

    @Override
    public boolean remove(int data) {

        if(this.size() == 0){
            return false;  //空链表直接返回null
        }

        Node node = searchNodeByData(data);
        Node temp = this.head;  // 需要找被删节点的前一个节点
        while (temp.next!=null) {
            if(temp.next.getData()==data){
                 temp.next = temp.next.next;
                 node.next = null;
                 return true;
            }else {
                temp=temp.next;
            }
        }
        System.out.println("无该节点!");
        return false;
    }

    /*删除全部指定值*/
    @Override
    public void removeAllKey(int key) {
        //因为删除一个节点需要前一个节点的连接，所以需要建立两个节点完成整个工程
        Node ahead=this.head;            //前一个节点
        int count = 0      ;                           //后一个节点（在cur中判断data是否与key相等），两个节点从头开始往后遍历
        while (ahead.next!=null) {              //当cur为空时完成遍历
            if(ahead.next.getData()==key) {     //在cur中判断data是否与key相等，如果相等则删除
                ahead.next= ahead.next.next;
                count ++;
                //先完成连接
                //连接完成后cur后移继续判断该cur.data是否为关键字，ahead不用动（因为已经删除该节点以后，只需cur后移，ahead仍为cur的前一个节点）
            }else {         //如果不相等，则两者均后移
                ahead=ahead.next;
            }
        }
        if (count == 0){
            System.out.println("没找到节点!");
        }
      /*  if(this.head.getData()==key) {//最后考虑头节点，如果相等再完成删除
            this.head=this.head.next;
        }*/
    }

    // 查找是否含有指定值的
    @Override
    public boolean contains(int data) {
        if(this.head==null){
            return false;  //空链表直接返回false
        }

        Node temp = this.head;  //
        while (temp.next!=null) {
            if(temp.next.getData()==data){
                return true;
            }else {
                temp=temp.next;
            }


        }
        return false;//完成遍历后没有找到，返回false
    }
    /* 按值查询 并返回节点*/
    @Override
    public Node searchNodeByData(int data) {
        if(this.size() ==0){
            return null;  //空链表直接返回null
        }

        Node temp = this.head;  //
        while (temp.next!=null) {
            if(temp.next.getData()==data){
                return temp.next;
            }else {
                temp=temp.next;
            }
        }
        return null;//完成遍历后没有找到，返回false
    }


    @Override
    public int size() {
        int count=0;
        Node temp = this.head;
        while (temp.next!=null) {//遍历链表，求出长度，返回长度 (不包含头节点)
            count++;
            temp=temp.next;
        }
        return count;
    }

    @Override
    public void display() {
        Node temp=this.head;
        if (temp.next ==null){
            System.out.println("链表为空");
            return;
        }
        while (temp!=null) {//设置循环遍历链表 完成打印
            System.out.println(temp.toString()+" ");
            temp=temp.next;
        }
    }
    @Override
    public boolean updateNodeByIndex(int index,int data){
        System.out.println("this.size()"+this.size());
        if(index<0||index>this.size()){  //判断位置合法性
            System.out.println("index位置不合法");
            return false;
        }
        Node node = searchNodeByIndex(index);
        if (node!=null){
            node.setData(data);
            return true ;
        }

        return false;
    }


    @Override
    public void clear() {
        this.head=null;
        // this.head= new Node(-1);
    }

    /*返回链表最小的节点 */
    @Override
    public  Node searchMinNode (){
        if (size()==0){
            throw new RuntimeException("当前没有节点 获取前驱失败");
        }
        if (size()==1){
            return this.head;
        }

        System.out.println("head"+this.head);
        Node minNodePre = this.head;
        Node minNode = this.head.next;
        Node pre =this.head.next;
        Node cur = this.head.next.next;
        while (cur != null) {
            if (cur.getData() < minNode.getData()) {
                minNodePre = pre;
                minNode = cur;
            }
            pre = cur;
            cur = cur.next;
        }
        return minNode;
    }
    /*找最小值的前驱节点  */
    @Override
    public  Node getMinNodePre() {
        if (size()==0){
            throw new RuntimeException("当前没有节点 获取前驱失败");
        }
        if (size()==1){
            return this.head;
        }

        System.out.println("head"+this.head);
        Node minNodePre = this.head;
        Node minNode = this.head.next;
        Node pre =this.head.next;
        Node cur = this.head.next.next;
        while (cur != null) {
            if (cur.getData() < minNode.getData()) {
                minNodePre = pre;
                minNode = cur;
            }
            pre = cur;
            cur = cur.next;
        }
        return minNodePre;
    }


    /*反转链表  创建新链表的方式   有效*/
    public static void reverseList(Node head){
        //如果当前链表为空，或者只有一个节点，无需反转，直接返回
        if(head.next == null || head.next.next == null) {
            return ;
        }

        //定义一个辅助的指针(变量)，帮助我们遍历原来的链表
        Node cur = head.next;
        Node next = null;// 指向当前节点[cur]的下一个节点
        Node newHead = new Node(0);
        //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端

        while(cur != null) {
            next = cur.next;        //先暂时保存当前节点的下一个节点，因为后面需要使用
            cur.next = newHead.next;//将cur的下一个节点指向新的链表的最前端
            newHead.next = cur;     //将cur 连接到新的链表上
            cur = next;//让cur后移
        }
        //将head.next 指向 newHead.next , 实现单链表的反转
        head.next = newHead.next;

    }
    /* 原地反转 有效*/
    public  Node  reverse_list(){
        if (this.head.next==null ) return this.head; // 没有节点
        if (this.head.next.next==null) return this.head; // 只有一个节点
        //至少有两个节点

        Node cur = this.head.next;
        this.head.next = null;
        Node next= null;
        while (cur != null){
            next = cur.next;
            cur.next = head;
            this.head = cur;
            // cur = cur.next;   nex 一直是head 不能这样写
            cur = next;
        }
        return head ; // 无法保留原头结点
    /*
        Node newHead = new Node(-100);
        newHead.next = this.head;

        Node temp=newHead;
        if (temp.next ==null){
            System.out.println("链表为空");

        }
        System.out.println("test");
        while (temp!=null) {//设置循环遍历链表 完成打印

            System.out.println(temp.toString()+" ");
            temp=temp.next;
        }
        return newHead;*/


    }

    /* 递归反转链表  (有问题)*/
    public  Node reverseList2(Node head){
        //如果当前链表为空，或者只有一个节点，无需反转，直接返回
        if (this.head.next==null ) return this.head; // 没有节点
        if (this.head.next.next==null) return this.head; // 只有一个节点


        return null;
//        Node pre = reverseList2(head.next);
//        head.next.next = head;
//        head.next = null;
//        return pre;
    }

    /*归并 合并两个有序链表  暂放*/
    public static void guibing (SLinkList list1,SLinkList linkList2){

    }

    /*链表 的排序  暂放*/
    public static void sortLinkList (SLinkList list1,SLinkList linkList2){

    }



}

// 排序， 找最值，归并


//定义HeroNode ， 每个HeroNode 对象就是一个节点
class Node {
    private int data;
    public Node next;; //指向下一个节点
    //构造器
    public Node(){

    }
    public Node(int data){
        this.data = data;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    //为了显示方法，我们重新toString
    @Override
    public String toString() {
        // 为什么里面不写next , 因为输出每个节点都会把后面的也输出
        return "Node [data=" + data +"]";
    }

}


class Test{
    public static void main(String[] args) {
        SLinkList sLinkList = new SLinkList();
        sLinkList.addLast(1);
        sLinkList.addLast(2);
        sLinkList.addLast(3);
        sLinkList.addLast(4);
        sLinkList.addLast(4);
        sLinkList.addLast(4);
        sLinkList.addLast(5);
        sLinkList.addLast(0);
        sLinkList.updateNodeByIndex(3,33);
        sLinkList.addIndex(4,1000); // 在标为4的位置插入1000, 下使之成为第5个元素
        sLinkList.display();
//        System.out.println( sLinkList.getMinNodePre());
//        System.out.println(sLinkList.searchMinNode());
        System.out.println("反转");
//        sLinkList.reverseList(sLinkList.getHead());
        sLinkList.reverse_list();
        sLinkList.display();

//        System.out.println("按值查询");
//        System.out.println( sLinkList.searchNodeByData(10));

//        System.out.println(sLinkList.remove(10));
//        sLinkList.removeAllKey(40);
//        sLinkList.display();
        // System.out.println(sLinkList.getHead().toString());
        // System.out.println( sLinkList.size());
        // sLinkList.clear();
        // sLinkList.display();

        // System.out.println( sLinkList.contains(3));

//        System.out.println("反转链表");
//        LinkList linkList2 = sLinkList.reverseList();
//        sLinkList.reverse_list(sLinkList.getHead());
//        sLinkList.display();
//        linkList2.display();
    }
}